#pragma once
#include <array>
#include <string>
#include <vector>
#ifdef DEBUG
#include <iostream>
#endif


class Integer
{
private:
	int sgn;
	std::vector<unsigned> num;
public:
	Integer();
	Integer(const Integer&);
	Integer(Integer&&);
	Integer(const int n);
	Integer(const unsigned n);
	Integer(const std::string &str);
public:
	Integer& operator=(const Integer&);
	Integer& operator=(Integer&&);
public:
	~Integer();
protected:
	static const unsigned MinBase, MaxBase;
public:
	std::string str() const;
	friend std::ostream& operator<<(std::ostream &out, const Integer &n);
private:
	static unsigned base;
	static void SetBase(const unsigned base);
	static const unsigned MulKaratsubaThreshold, MulFFTThreshold;
	static const unsigned SqrKaratsubaThreshold, SqrFFTThreshold;
	static const Integer BigPrime;
	static const Integer PrimitiveRoot, InversePrimitiveRoot;
	static const std::array<Integer, 32> ExpPrimitiveRoot, ExpInversePrimitiveRoot;
public:
	friend unsigned _unsigned(const Integer &n);
	friend bool operator==(const Integer &lhs, const Integer &rhs);
	friend bool operator!=(const Integer &lhs, const Integer &rhs);
	friend bool operator<(const Integer &lhs, const Integer &rhs);
	friend bool operator<=(const Integer &lhs, const Integer &rhs);
	friend bool operator>(const Integer &lhs, const Integer &rhs);
	friend bool operator>=(const Integer &lhs, const Integer &rhs);
	Integer operator-() const;
	friend Integer operator-(Integer &&n);
	unsigned Bits() const;
	bool Bit(const unsigned bit) const;
	friend Integer operator+(const Integer &lhs, const Integer &rhs);
	friend Integer operator+(const Integer &lhs, Integer &&rhs);
	friend Integer operator+(Integer &&lhs, const Integer &rhs);
	friend Integer operator+(Integer &&lhs, Integer &&rhs);
	Integer& operator+=(const Integer &addend);
	Integer& operator++();
	Integer operator++(int);
	friend Integer operator-(const Integer &lhs, const Integer &rhs);
	friend Integer operator-(const Integer &lhs, Integer &&rhs);
	friend Integer operator-(Integer &&lhs, const Integer &rhs);
	friend Integer operator-(Integer &&lhs, Integer &&rhs);
	Integer& operator-=(const Integer &subtrahend);
	Integer& operator--();
	Integer operator--(int);
	friend Integer operator*(const Integer &lhs, const Integer &rhs);
	Integer operator*(const int factor) const;
	Integer operator*(const unsigned factor) const;
	friend Integer operator*(const int factor, const Integer &multiplier);
	friend Integer operator*(const unsigned factor, const Integer &multiplier);
	Integer& operator*=(const Integer &factor);
	Integer& operator*=(const int factor);
	Integer& operator*=(const unsigned factor);
	friend Integer Square(const Integer &n);
private:
	unsigned SingleLimbDivide(const Integer &divisor, Integer &remainder) const;
public:
	friend Integer Divide(const Integer &dividend, const Integer &divisor, Integer &remainder);
	friend Integer Divide(const Integer &dividend, const int divisor, unsigned &remainder);
	friend Integer Divide(const Integer &dividend, const unsigned divisor, unsigned &remainder);
	friend Integer operator/(const Integer &lhs, const Integer &rhs);
	Integer operator/(const int divisor) const;
	Integer operator/(const unsigned divisor) const;
	Integer& operator/=(const Integer &divisor);
	Integer& operator/=(const int divisor);
	Integer& operator/=(const unsigned divisor);
	friend Integer operator%(const Integer &lhs, const Integer &rhs);
	unsigned operator%(const int divisor) const;
	unsigned operator%(const unsigned divisor) const;
	Integer& operator%=(const Integer &divisor);
	Integer& operator%=(const int divisor);
	Integer& operator%=(const unsigned divisor);
	friend Integer operator&(const Integer &lhs, const Integer &rhs);
	Integer& operator&=(const Integer &n);
	friend Integer operator|(const Integer &lhs, const Integer &rhs);
	Integer& operator|=(const Integer &n);
	friend Integer operator^(const Integer &lhs, const Integer &rhs);
	Integer& operator^=(const Integer &n);
	Integer operator<<(const int n) const;
	Integer operator<<(const unsigned n) const;
	Integer& operator<<=(const int n);
	Integer& operator<<=(const unsigned n);
	Integer operator>>(const int n) const;
	Integer operator>>(const unsigned n) const;
	Integer& operator>>=(const int n);
	Integer& operator>>=(const unsigned n);
	friend Integer IntegerRoot(const Integer &n, const unsigned root);
	static Integer Random(const unsigned size);
private:
	static Integer Mask(const unsigned n);
	Integer ModBigPrime() const;
	static std::array<Integer, 32> InitExpTable(bool dir);
	static void FFT(std::vector<Integer> &coefficient);
	static void FFT(std::vector<Integer> &coefficient1, std::vector<Integer> &coefficient2);
	static void iFFT(std::vector<Integer> &coefficient);
};

namespace std
{
	template <typename T> bool IsEven(const T &n) {return !(n & 1);}
	template <typename T> bool IsOdd(const T &n) {return n & 1;}
	bool IsEven(const Integer &n);
	bool IsOdd(const Integer &n);
	template <typename T> int sgn(const T &n)
	{
		return n == T(0) ? 0 : (n > T(0) ? 1 : -1);
	}
	template <typename T> T abs(const T &n)
	{
		return n < T(0) ? -n : n;
	}
	template <typename T> T Square(const T &n)
	{
		return n * n;
	}
	template <typename T> T Exp(const T &n, const Integer &exp)
	{
		if (exp < 0)
			throw;
		else if (exp == 0)
			return T(1);

		T product(n);

		for (int i = exp.Bits() - 1; --i >= 0;)
		{
			product = Square(product);

			if (exp.Bit(i))
				product *= n;
		}

		return std::move(product);
	}
}
